package org.usmile.algorithms.learn.graph.direction;

import org.usmile.algorithms.learn.graph.Graph;

import java.util.ArrayList;
import java.util.List;

public class GraphDFSR {
    /**
     * 深度优先遍历 递归
     */
    public List<Integer> dfs(Graph graph) {
        if (graph == null) {
            return new ArrayList<>();
        }

        List<Integer> result = new ArrayList<>();
        boolean[] visited = new boolean[graph.getV()];
        for (int v = 0; v < graph.getV(); v++) {
            if (!visited[v]) {
                dfs(graph, v, visited, result);
            }
        }

        return result;
    }

    private void dfs(Graph graph, int v, boolean[] visited, List<Integer> result) {
        visited[v] = true;
        result.add(v);

        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                dfs(graph, w, visited, result);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new DirectionAdjSet(8);
        graph.addEdge(0, 2);
        graph.addEdge(0, 7);
        graph.addEdge(5, 6);

        System.out.println(new GraphDFSR().dfs(graph));
    }
}
